Secure Anonymous Database Searching has been employed when different parties possess data of mutual interest. See, for example, M. Raykova et al., “Secure Anonymous Database Search,” Cloud Computing Security Workshop (CCSW) (Nov. 2009); and V. Pappas et al., “Private Search in the Real World,” Proc. of the 27th Annual Computer Security Applications Conference (ACSAC) (Dec. 2011). Generally, secure anonymous database searching techniques allow a client to search information residing on a server without revealing the identity of the client or the content of the query to the server. At the same time, the server is protected in that the query capability is only granted to authorized clients and the clients do not learn anything unrelated to the query.
In one exemplary implementation, the server S encrypts the database with a separate key for each entry and provides the encrypted database to an index server IS. In addition, the server S creates an encrypted search structure that is also given to the index server IS. When a client C wants to query the database, the client C encrypts the query, sends it to the index server IS, and the query is executed blindly by the index server IS using the encrypted search structure.
In order to reduce the leakage of information about the query and the response, Bloom filters (BFs) of encrypted keywords have been used as the search structure. Heterogeneous elements, such as keywords, can be inserted into a Bloom filter. At a later time, a user can check whether a particular element was inserted into the Bloom filter by checking that several bits of the Bloom filter are set to one.
In a secure anonymous database searching system that employs Bloom filters, each encrypted database row that is stored by the index server IS has an associated encrypted Bloom filter. Checking encrypted keywords (supplied by the client C) with the Bloom filter allows the index server IS to determine if that keyword was associated with the corresponding database record, and to return the required records. Since the keywords are encrypted, the index server IS does not learn the content of the query.
Eu-Jin Goh, “Secure Indexes,” Cryptology ePrint Archive: Report 2003/216 (http://eprint.iacr.org/2003/216), improves the scalability of such secure anonymous database searching systems by proposing the use of a tree of Bloom filters. Generally, a binary tree is built on top of the Bloom filters corresponding to database rows, with internal nodes being Bloom filters that include all the keywords included in any of the Bloom filters of the sub-tree. The database can now be searched more quickly, since the matching database row is identified by going down the Bloom filter tree.
A need remains for secure anonymous database searching systems that can process more complex queries than just keyword search. In particular, a need remains for secure anonymous database searching systems that can process queries requiring a formula evaluation, such as formulas, range queries, negations and approximations. Yet another need remains for secure anonymous database searching systems that can process queries requiring a formula evaluation without revealing whether each term of the formula is matched by the Bloom filter.